class Solution {
public:
    vector<string> str_vec = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans;
    string tmp;
    void dfs(int k, string& digits){
        if(digits.size() == tmp.size()){
            ans.emplace_back(tmp);
            return;
        }
        for(auto& chr: str_vec[digits[k]-'0']){
            tmp.push_back(chr);
            dfs(k+1, digits);
            tmp.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ans;
        dfs(0, digits); 
        return ans;
    }
};